#include<bits/stdc++.h>
using namespace std;
struct node
{
    vector<node*> childs;
    bool flag;
    node()
    {
        childs=vector<node*>(26);
        flag=false;
    }
};

class Solution {
public:
    string replaceWords(vector<string>& dictionary, string sentence) {
        stringstream ss(sentence);
        vector<string> rev;
        string word;
        node* root=new node();
        string ret="";
        node* cur=root;
        while(getline(ss,word,' '))
            rev.push_back(word);
        for(string s:dictionary)
        {
            for(char ch:s)
            {
                ch-='a';
                if(cur->childs[ch]==nullptr) cur->childs[ch]=new node();
                cur=cur->childs[ch];
            }
            cur->flag=true;
            cur=root;
        }
        word.clear();
        cur=root;
        for(auto s:rev)
        {
            if(!ret.empty()) ret+=" ";
            for(char ch:s)
            {
                int k=ch-'a';
                if(cur->childs[k]!=nullptr)
                {
                    word+=ch;
                    cur=cur->childs[k];
                    if(cur->flag)   break;
                }
                else
                {
                    word=s;
                    break;
                }
            }
            ret+=word;
            word.clear();
            cur=root;
        }
        return ret;
    }
    
};

int main()
{

    string s="the cattle was rattled by the battery";
    vector<string> vec={"cat","bat","rat"};
    Solution so;
    so.replaceWords(vec,s);
}